package ljl.alg.wangzheng_camp.round1.dp;

import java.util.Arrays;

/**
 * 我反手就开始抄答案
 * 抄归抄，不至于看不懂吧应该我就不看解析了直接读一读答案然后抄下来
 * */
public class _322_coin_change {
    
    class search {
        /**
         * 先来背诵一把 记忆化搜索，除了不会写，没啥难的
         *
         * 非常慢啊非常慢
         *
         * */
        public int coinChange(int[] coins, int amount) {
            return count(coins, amount, new int[amount + 1]);
        }
        int count(int[] coins, int remain, int[] cache) {
            if (remain < 0) return -1;
            if (remain == 0) return 0;
            if (cache[remain] != 0) return cache[remain];
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                int res = count(coins, remain - coin, cache);
                if (res >= 0 && res < min) {
                    min = res + 1;
                }
            }
            cache[remain] = min == Integer.MAX_VALUE ? -1 : min;
            return cache[remain];
        }
    }
    
    class dp {
        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, amount + 1);
            dp[0] = 0;
            for (int i = 1; i <= amount; i++) {
                for (int coin : coins) {
                    if (coin <= i) {
                        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    }
                }
            }
            return dp[amount] == amount + 1 ? -1 : dp[amount];
        }
    }
    
    class of2 {
        public class Solution {
            public int coinChange(int[] coins, int amount) {
                int max = amount + 1;
                int[] dp = new int[amount + 1];
                Arrays.fill(dp, max);
                dp[0] = 0;
                for (int i = 1; i <= amount; i++) {
                    for (int j = 0; j < coins.length; j++) {
                        if (coins[j] <= i) {
                            dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                        }
                    }
                }
                return dp[amount] > amount ? -1 : dp[amount];
            }
        }
    }
}
